In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the Foster graph is a bipartite 3-

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegr ...

with 90 vertices and 135 edges. The Foster graph is

Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

and has

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blu ...

3, radius 8, diameter 8 and girth 10. It is also a 3- vertex-connected and 3- edge-connected graph. It has

queue number In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings. Defi ...

2 and the upper bound on the

book thickness In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie ...

is 4. All the cubic

distance-regular graph In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . ...

s are known. The Foster graph is one of the 13 such graphs. It is the unique distance-transitive graph with

intersection array In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . ...

. It can be constructed as the incidence graph of the

partial linear space A partial linear space (also semilinear or near-linear space) is a basic incidence structure in the field of incidence geometry, that carries slightly less structure than a linear space. The notion is equivalent to that of a linear hypergraph. Defi ...

which is the unique triple

cover Cover or covers may refer to: Packaging * Another name for a lid * Cover (philately), generic term for envelope or package * Album cover, the front of the packaging * Book cover or magazine cover ** Book design ** Back cover copy, part of co ...

with no 8-gons of the

generalized quadrangle In geometry, a generalized quadrangle is an incidence structure whose main feature is the lack of any triangles (yet containing many quadrangles). A generalized quadrangle is by definition a polar space of rank two. They are the with ''n'' = 4 ...

''GQ''(2,2). It is named after R. M. Foster, whose ''

Foster census In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 and f(v_1) = v_2. In ot ...

'' of cubic

symmetric graph In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 and f(v_1) = v_2. In oth ...

s included this graph. The bipartite half of the Foster graph is a

and a

locally linear graph In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be ...

. It is one of a finite number of such graphs with degree six.

Algebraic properties

The automorphism group of the Foster graph is a group of order 4320. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Foster graph is a

. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. According to the ''Foster census'', the Foster graph, referenced as F90A, is the only cubic symmetric graph on 90 vertices. Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002. The characteristic polynomial of the Foster graph is equal to

(x-3) (x-2)^9 (x-1)^ x^ (x+1)^ (x+2)^9 (x+3) (x^2-6)^

Gallery

Image:Foster graph colored.svg, Foster graph colored to highlight various cycles. Image:Foster graph 2COL.svg, The

of the Foster graph is 2. Image:Foster_graph_3color_edge.svg, The

of the Foster graph is 3.

References

*. *. *{{citation , last = Van Maldeghem , first = Hendrik , title = Ten exceptional geometries from trivalent distance regular graphs , journal = Annals of Combinatorics , volume = 6 , issue = 2 , year = 2002 , pages = 209–228 , mr = 1955521 , doi = 10.1007/PL00012587. Individual graphs Regular graphs